﻿#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
struct ListNode 
{
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

struct ListNode* seckmid(struct ListNode* head)
{
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

struct ListNode* inverted(struct ListNode* head)
{
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;
    while (cur)
    {
        struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

bool chkPalindrome(struct ListNode* A)
{
    struct ListNode* mid = seckmid(A);
    struct ListNode* middle=inverted(mid);
    while (A && middle)
    {
        if (A->val != middle->val)
        {
            return false;
        }
        A = A->next;
        middle = middle->next;
    }
    return true;
}
int main()
{
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = 1;
    struct ListNode* node1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    node1->val = 2;
    struct ListNode* node2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    node2->val = 3;
    struct ListNode* node3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    node3->val = 2;
    struct ListNode* node4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    node4->val = 1;
    head->next = node1;
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = NULL;
    bool n = chkPalindrome(head);
    printf("%d\n", n);
    return 0;
}